package com.leetcode.August;

import javax.swing.tree.TreeNode;
import java.util.Arrays;


/**
 * @Description: 106. 从中序与后序遍历序列构造二叉树
 * 灵神
 * @Author: Mr.Fxy
 * @CreateTime: 2024-08-31 09:11
 */
public class LC106从中序与后序遍历序列构造二叉树 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = postorder.length;
        if (n == 0) {
            return null;
        }
        int leftSize = indexOf(inorder, postorder[n - 1]); // 左子树的大小
        int[] in1 = Arrays.copyOfRange(inorder, 0, leftSize);
        int[] in2 = Arrays.copyOfRange(inorder, leftSize + 1, n);
        int[] post1 = Arrays.copyOfRange(postorder, 0, leftSize);
        int[] post2 = Arrays.copyOfRange(postorder, leftSize, n - 1);
        TreeNode left = buildTree(in1, post1);
        TreeNode right = buildTree(in2, post2);
        return new TreeNode(postorder[n - 1], left, right);
    }

    private int indexOf(int[] inorder, int i) {
        for (int j = 0; ; j++) {
            if (inorder[j] == i)
                return j;
        }
    }
}
